In many computing environments, caches are used to transparently store data items in order to serve that content faster in response to future requests. Many types of data items, for example, video, images, documents, query results, objects, or other types of data structures may be cached. Caching can reduce the latency involved in serving content to requesters. Caching can also reduce network traffic by enabling a server to serve content that is frequently requested from a local storage rather than by making frequent retrievals from a remote location over a wide area network.
In web environments, caching is frequently used by web browsers as well as by servers. The servers that may use caching include origin servers as well as proxy servers. A web browser, executing on a client device, may locally cache data so that the number of Hyper Text Transfer Protocol (HTTP) requests to remote web servers may be reduced. A proxy server may maintain a cache so that it may reduce repeated requests to origin servers for data items that are repeatedly requested by clients. For example, when a proxy server encounters a request for an object for the first time, it requests that object from an origin server over a wide area network and stores a copy of it in a local cache. Subsequent requests for that object may be serviced by retrieving that object from the local cache rather than from the remotely located origin server. Upon subsequent requests, the proxy server would first seek to retrieve the object from the local cache, and would request the origin server for the object only if the sought object is not cached. However, in many environments, proxy servers such as HTTP proxy servers, concurrently service numerous requests for various types of data items. Concurrently servicing numerous requests for large data items can lead to scalability and performance concerns with respect to caching.